﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GameLibrary.AI.Knapsack
{
    /// <summary>
    /// algorithm for GKP.
    /// </summary>
    public static class MTHG
    {
        #region FeasiblityType
        /// <summary>
        /// Choose feasiblity type used in MTHG
        /// </summary>
        public enum FeasiblityType
        {
            /// <summary>
            /// fij = pij
            /// </summary>
            Profit,
            /// <summary>
            /// fij = pij/wij
            /// </summary>
            ProfitWeightRatio,
            /// <summary>
            /// fij = -wij
            /// </summary>
            NegativeWeight,
            /// <summary>
            /// fij = -wij/ci
            /// </summary>
            NegativeWeigitCapacityRatio
        }
        #endregion

        #region MTHG
        /*
         * Source:
         *      Knapsack Problems: Algorithms and Computer Implementations by Silvano Martello and Paolo Toth
         * Page: 206
         * 
         * 0: procedure MTHG
         * 
         * 1: input n,m,(pij),(wij),(ci),(fij);
         * 2: output zh,(yi),feas;
         * 
         * 3: begin
         * 4:       M:={1,...,m}
         * 5:       U:={1,...,n}
         * 6:       comment:initial solution;
         * 7:       feas:="yes"
         * 8:       for i:=1 to m do _ci:=ci;
         * 9:       zh:=0;
         * 10:      while U!= null and feas = "yes" do
         * 11:      begin
         * 12:       |   d* := -inf
         * 13:       |   for each j belong to U do
         * 14:       |       begin
         * 15:       |        |   Fj:={i belong to M: wij <= _ci}
         * 16:       |        |   if Fj = null then feas := "no"
         * 17:       |        |   else
         * 18:       |        |       begin
         * 19:       |        |        |   i':=arg max {fij:i belong to Fj}
         * 20:       |        |        |   if Fj-{i'} = null then d:= +inf
         * 21:       |        |        |   else d:=fi'j - max2{fij : i belong to Fj}
         * 22:       |        |        |   if d > d* then
         * 23:       |        |        |       begin
         * 24:       |        |        |        |  d*:=d;
         * 25:       |        |        |        |  i*:=i';
         * 26:       |        |        |        |  j*:=j;
         * 27:       |        |        |       end
         * 28:       |        |       end
         * 29:       |       end
         * 30:       |   if feas = "yes" then
         * 31:       |       begin
         * 32:       |        |  yj*:=i*;
         * 33:       |        |  zh:=zh+pi*j*;
         * 34:       |        |  _ci*:=_ci*-wi*j*;
         * 35:       |        |  U:=U-{j*};
         * 36:       |       end
         * 37:      end
         * 
         * 38:      comment: improvement;
         * 39:      if feas = "yes" then
         * 40:          for j:=1 to n do
         * 41:              begin
         * 42:               |  i'=yj;
         * 43:               |  A:={pij; i belong to M-{i'}, wij <= _ci}
         * 44:               |  if A != null then
         * 45:               |          begin
         * 46:               |           |   let pi''j = max A;
         * 47:               |           |   if pi''j > pi'j then 
         * 48:               |           |          begin
         * 49:               |           |           |  yj:=i'';
         * 50:               |           |           |  zh := zh-pi'j+pi''j;
         * 51:               |           |           |  _ci'=_ci'+wi'j;
         * 52:               |           |           |  _ci'':=_ci''-wi''j;
         * 53:               |           |          end
         * 54:               |          end
         * 55:              end
         * 56: end
         * 
         */ 
        public static void GetResult(
            //input
            int n, //n, item number
            int m, //m, knapsack number
            int[,] pij, //(pij),  profit of item j if insert into knapsack i
            int[,] wij, //(wij),  weight of item j if insert into knapsack i
            int[] ci, //(ci) capacity of knapsack i
            FeasiblityType type, // generate (fij) inside procedure
            // output

           out int zh, // zh
           out int[] yj, //(yj) knapsack to which item j is assigned
           out YesNo feas // feas
            )
        {
            #region init output variables
            yj = new int[n];
            #endregion
            #region fij
            double[,] fij = Getfij(type, pij, wij, ci);           
            #endregion
            #region initial solution
            #region line 4 - 9
            // line 4 and 5
            HashSet<int> M = new HashSet<int>(); // M
            HashSet<int> U = new HashSet<int>(); // U
            for (int i = 0; i < m; i++) // knapsack list
                M.Add(i);
            for (int j = 0; j < n; j++) // item list
                U.Add(j);
            #endregion
            // feas = "yes"
            feas = YesNo.yes;
            int[] _ci = new int[m]; // knapsack capcity
            ci.CopyTo(_ci,0);
            // zh = 0
            zh = 0; // total value zh
            while (U.Count > 0 && feas == YesNo.yes) // exist item not assigned and exist feasible solution
            {
                // d* = - inf
                double dstar = double.NegativeInfinity;  
                int istar = -1; // which knapsack was selected
                int jstar = -1; // which item was selected
                foreach (int j in U) // for each j in U do
                {
                    // Fj :={i brlong to M: wij <=_ci}
                    List<int> Fj = GetFj(M, j, wij, _ci);  // item i's weight which less than knapsack i's capcity
                    if (Fj.Count <= 0) // no such item
                        feas = YesNo.no; // no feasible solution
                    else
                    {
                        // 1st    -- i
                        // 2nd -- fij
                        SortedList<int, double> max = GetMaxList(j,Fj, fij); 
                        var firstLargest = max.First(); // i' = argmax( fij : i belong to Fj);

                        double d ;// difference between largest and second largest
                        if (Fj.Count <= 1) // Fj-{i'} = null
                            d = double.PositiveInfinity;
                        else
                        {
                            max.Remove(firstLargest.Key);
                            var secondLargest = max.First();
                            d = firstLargest.Value - secondLargest.Value;
                        }

                        if (d > dstar) // if d > d*
                        {
                            dstar = d; // d* = d
                            istar = firstLargest.Key; // i* = i'
                            jstar = j; // j* = j
                        }
                    }
                }
                if (feas == YesNo.yes)
                {
                    yj[jstar] = istar; // yj* = i*;
                    zh = zh + pij[istar, jstar];
                    _ci[istar] = _ci[istar] - wij[istar, jstar];
                    U.Remove(jstar);
                    #region debug
                    Console.WriteLine("j* = " + (jstar+1) + " d* = " + dstar + "yj* = " + (yj[jstar]+1) + "_ci[yj*] = " + _ci[yj[jstar]]);
                    Console.WriteLine();
                    #endregion
                }
            }
            #region debug
            Console.WriteLine("zh = " + zh);
            Console.Write("yj = (");
            foreach(var i in yj)
                Console.Write(" " + (i+1) + " ,");
            Console.WriteLine(")");
            Console.WriteLine("_ci = (");
            foreach(var i in _ci)
                Console.WriteLine(" " + i + " ,");
            Console.WriteLine(")");
            #endregion
            #endregion
            #region improvement
            if (type != FeasiblityType.Profit)
            if(feas == YesNo.yes)
                for (int j = 0; j < n; j++)
                {
                    int iqout = yj[j];
                    var A = GetA(j, iqout, M, pij, wij, _ci);
                    if (A.Count > 0)
                    {
                        var kv = A.First(); // let pi''j = max A
                        if (kv.Value > pij[iqout, j]) // pi''j > pi'j
                        {
                            yj[j] = kv.Key; // yj = i''
                            zh = zh - pij[iqout, j] + kv.Value; // zh = zh - pi'j + pi''j
                            _ci[iqout] = _ci[iqout] + wij[iqout, j];
                            _ci[kv.Key] = _ci[kv.Key] - wij[kv.Key, j];
                        }
                    }
                }
            #region debug
            Console.WriteLine("zh = " + zh);
            Console.Write("yj = (");
            foreach(var i in yj)
                Console.Write(" " + i + " ,");
            Console.WriteLine(")");
            #endregion
            #endregion
        }
        #region Get fij
        private static double[,] Getfij(FeasiblityType type, int[,] pij, int[,] wij, int[] ci)
        {
            double[,] fij = null;
            switch (type)
            {
                case FeasiblityType.Profit:
                    fij = fijEquals_pij(pij);
                    break;
                case FeasiblityType.ProfitWeightRatio:
                    fij = fijEquals_pijdividedbywij(pij, wij);
                    break;
                case FeasiblityType.NegativeWeight:
                    fij = fijEquals_negativewij(wij);
                    break;
                case FeasiblityType.NegativeWeigitCapacityRatio:
                    fij = fijEquals_negativewijdividedbyci(wij, ci);
                    break;
            }            
            return fij;
        }
        private static double[,] fijEquals_pij(int[,] pij)
        {
            double[,] fij = new double[pij.GetLength(0), pij.GetLength(1)];
            for (int i = 0; i < pij.GetLength(0); i++)
                for (int j = 0; j < pij.GetLength(1); j++)
                    fij[i, j] = pij[i, j];
            return fij;
        }
        private static double[,] fijEquals_pijdividedbywij(int[,] pij, int[,] wij)
        {
            double[,] fij = new double[pij.GetLength(0), pij.GetLength(1)];
            for (int i = 0; i < pij.GetLength(0); i++)
                for (int j = 0; j < pij.GetLength(1); j++)
                    fij[i, j] = pij[i, j] / wij[i, j];
            return fij;
        }
        private static double[,] fijEquals_negativewij(int[,] wij)
        {
            double[,] fij = new double[wij.GetLength(0), wij.GetLength(1)];
            for (int i = 0; i < wij.GetLength(0); i++)
                for (int j = 0; j < wij.GetLength(1); j++)
                    fij[i, j] = -wij[i, j];
            return fij;
        }
        private static double[,] fijEquals_negativewijdividedbyci(int[,] wij, int[] ci)
        {
            double[,] fij = new double[wij.GetLength(0), wij.GetLength(1)];
            for (int i = 0; i < wij.GetLength(0); i++)
                for (int j = 0; j < wij.GetLength(1); j++)
                    fij[i, j] = (-1.0 * wij[i, j]) / ci[i];
            return fij;
        }
        #endregion
        #region Get Fj
        private static List<int> GetFj(
            HashSet<int> M,
            int j,
            int[,] wij,
            int[] _ci
            )
        {
            List<int> Fj = new List<int>();
            foreach(int i in M)
            {
                if(wij[i,j]<=_ci[i])
                    Fj.Add(i);
            }
            return Fj;
        }
        #endregion
        #region Get arg max list
        private static SortedList<int, double> GetMaxList(int j, List<int> Fj, double[,] fij)
        {
            SortedList<int, double> list = new SortedList<int, double>();
            foreach (int i in Fj)
                list.Add(i, fij[i, j]);
            return list;
        }

        #endregion
        #region Get A
        private static SortedList<int,int> GetA(int j, int iqout, HashSet<int> M,int[,] pij, int[,] wij, int[] _ci)
        {
            SortedList<int, int> A = new SortedList<int, int>();
            foreach (var i in M)
            {
                if (i == iqout) // M-{i'}
                    continue;
                if (wij[i, j] <= _ci[i])
                    A.Add(i,pij[i,j]);
            }
            return A;
        }
        #endregion
        #endregion
    }
}
